import java.util.ArrayList;
import java.util.List;

/**
 * 1758. 生成交替二进制字符串的最少操作数
 * https://leetcode-cn.com/problems/minimum-changes-to-make-alternating-binary-string/
 */
public class Solutions_1758 {
    public static void main(String[] args) {
        String s1 = "0100";  // output: 1
        String s2 = "10";  // output: 0
        String s3 = "1111";  // output: 2

        List<String> inputs = new ArrayList<>();
        inputs.add(s1);
        inputs.add(s2);
        inputs.add(s3);

        for (String input : inputs) {
            int result = minOperations(input);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：贪心法
     * 比较将字符串 s 替换成 "0101" 交替形式和 "1010" 交替形式的最少替换次数
     * 关键：使用位运算来实现 1 和 0 的交替
     * 1 ^ 1 == 0
     * 0 ^ 1 == 1
     */
    public static int minOperations(String s) {
        char[] arr = s.toCharArray();
        // "0101" 的交替形式，最少需要操作 ans1 次
        int ans1 = method(arr, 0);
        if (ans1 == 0) {
            return 0;
        }
        // "1010" 的交替形式，最少需要操作 ans2 次
        int ans2 = method(arr, 1);
        // 哪个的操作次数最少，就选择替换成哪种形式
        return Math.min(ans1, ans2);
    }

    public static int method(char[] arr, int start) {
        int cnt = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] - '0' != start) {
                // 替换 1 次
                cnt ++;
            }
            // 1 ^ 1 == 0
            // 0 ^ 1 == 1
            start ^= 1;
        }
        return cnt;
    }
}
